home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / depend.cpp < prev    next >
C/C++ Source or Header  |  1999-05-14  |  16KB  |  480 lines
  1. // $Id: depend.cpp,v 1.6 1999/03/10 19:59:21 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "config.h"
  11. #include <time.h>
  12. #include "control.h"
  13. #include "ast.h"
  14. #include "semantic.h"
  15.  
  16. //
  17. // Note that the types are ordered based on on the subtype relationship. We reverse
  18. // the order here because the desired order for processing is the supertype relationship.
  19. //
  20. inline void TypeCycleChecker::ReverseTypeList()
  21. {
  22.     int head,
  23.         tail;
  24.     for (head = 0, tail = type_list.Length() - 1; head < tail; head++, tail--)
  25.     {
  26.         TypeSymbol *temp = type_list[head];
  27.         type_list[head] = type_list[tail];
  28.         type_list[tail] = temp;
  29.     }
  30.  
  31.     return;
  32. }
  33.  
  34.  
  35. void TypeCycleChecker::PartialOrder(Tuple<Semantic *> &semantic, int start)
  36. {
  37.     type_list.Reset();
  38.  
  39.     //
  40.     // assert that the "index" of all types that should be checked is initially set to OMEGA
  41.     //
  42.     for (int i = start; i < semantic.Length(); i++)
  43.     {
  44.         Semantic *sem = semantic[i];
  45.  
  46.         for (int k = 0; k < sem -> compilation_unit -> NumTypeDeclarations(); k++)
  47.         {
  48.             AstClassDeclaration *class_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> ClassDeclarationCast();
  49.             AstInterfaceDeclaration *interface_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> InterfaceDeclarationCast();
  50.             if (class_declaration || interface_declaration)
  51.             {
  52.                 SemanticEnvironment *env = (class_declaration ? class_declaration -> semantic_environment
  53.                                                               : interface_declaration -> semantic_environment);
  54.                 if (env) // type was successfully compiled thus far?
  55.                 {
  56.                     TypeSymbol *type = env -> Type();
  57.                     if (type -> index == OMEGA)
  58.                        ProcessSubtypes(type);
  59.                 }
  60.             }
  61.         }
  62.     }
  63.  
  64.     ReverseTypeList();
  65.  
  66.     return;
  67. }
  68.  
  69.  
  70. void TypeCycleChecker::PartialOrder(SymbolSet &types)
  71. {
  72.     //
  73.     // assert that the "index" of all types that should be checked is initially set to OMEGA
  74.     //
  75.     for (TypeSymbol *type = (TypeSymbol *) types.FirstElement(); type; type = (TypeSymbol *) types.NextElement())
  76.     {
  77.         if (type -> index == OMEGA)
  78.             ProcessSubtypes(type);
  79.     }
  80.  
  81.     ReverseTypeList();
  82.  
  83.     return;
  84. }
  85.  
  86.  
  87. void TypeCycleChecker::ProcessSubtypes(TypeSymbol *type)
  88. {
  89.     stack.Push(type);
  90.     int indx = stack.Size();
  91.     type -> index = indx;
  92.  
  93.     type -> subtypes_closure = new SymbolSet;
  94.     type -> subtypes_closure -> Union(*(type -> subtypes));
  95.     for (TypeSymbol *subtype = (TypeSymbol *) type -> subtypes -> FirstElement();
  96.                      subtype;
  97.                      subtype = (TypeSymbol *) type -> subtypes -> NextElement())
  98.     {
  99.         if (subtype -> index == OMEGA)
  100.              ProcessSubtypes(subtype);
  101.         type -> index = Min(type -> index, subtype -> index);
  102.         type -> subtypes_closure -> Union(*(subtype -> subtypes_closure));
  103.     }
  104.  
  105.     if (type -> index == indx)
  106.     {
  107.         TypeSymbol *scc_subtype;
  108.         do
  109.         {
  110.             scc_subtype = stack.Top();
  111.             scc_subtype -> index = INFINITY;
  112.             *(scc_subtype -> subtypes_closure) = *(type -> subtypes_closure);
  113.             type_list.Next() = scc_subtype;
  114.             stack.Pop();
  115.         } while (scc_subtype != type);
  116.     }
  117.  
  118.     return;
  119. }
  120.  
  121.  
  122. ConstructorCycleChecker::ConstructorCycleChecker(AstClassBody *class_body)
  123. {
  124.     for (int k = 0; k < class_body -> NumConstructors(); k++)
  125.     {
  126.         AstConstructorDeclaration *constructor_declaration = class_body -> Constructor(k);
  127.         if (constructor_declaration -> index == OMEGA)
  128.             CheckConstructorCycles(constructor_declaration);
  129.     }
  130.  
  131.     return;
  132. }
  133.  
  134.  
  135. void ConstructorCycleChecker::CheckConstructorCycles(AstConstructorDeclaration *constructor_declaration)
  136. {
  137.     stack.Push(constructor_declaration);
  138.     int indx = stack.Size();
  139.     constructor_declaration -> index = indx;
  140.  
  141.     AstConstructorDeclaration *called_constructor_declaration = NULL;
  142.  
  143.     AstConstructorBlock *constructor_block = constructor_declaration -> constructor_body;
  144.     if (constructor_block -> explicit_constructor_invocation_opt)
  145.     {
  146.         AstThisCall *this_call = constructor_block -> explicit_constructor_invocation_opt -> ThisCallCast();
  147.         MethodSymbol *called_constructor = (MethodSymbol *) (this_call ? this_call -> symbol : NULL);
  148.  
  149.         if (called_constructor)
  150.         {
  151.             called_constructor_declaration = (AstConstructorDeclaration *) called_constructor -> method_or_constructor_declaration;
  152.  
  153.             if (called_constructor_declaration -> index == OMEGA)
  154.                 CheckConstructorCycles(called_constructor_declaration);
  155.             constructor_declaration -> index = Min(constructor_declaration -> index, called_constructor_declaration -> index);
  156.         }
  157.     }
  158.  
  159.     if (constructor_declaration -> index == indx)
  160.     {
  161.         //
  162.         // If the constructor_declaration is alone in its strongly connected component (SCC),
  163.         // and it does not form a trivial cycle with itsself, pop it, mark it and return;
  164.         //
  165.         if (constructor_declaration == stack.Top() && constructor_declaration != called_constructor_declaration)
  166.         {
  167.             stack.Pop();
  168.             constructor_declaration -> index = INFINITY;
  169.         }
  170.         //
  171.         // Otherwise, all elements in the stack up to (and including) constructor_declaration form an SCC.
  172.         // Pop them off the stack, in turn, mark them and issue the appropriate error message.
  173.         //
  174.         else
  175.         {
  176.             do 
  177.             {
  178.                 called_constructor_declaration = stack.Top();
  179.                 stack.Pop();
  180.                 called_constructor_declaration -> index = INFINITY;
  181.  
  182.                 constructor_block = (AstConstructorBlock *) called_constructor_declaration -> constructor_body;
  183.                 AstMethodDeclarator *constructor_declarator = called_constructor_declaration -> constructor_declarator;
  184.  
  185.                 Semantic *sem = called_constructor_declaration -> constructor_symbol
  186.                                                                -> containing_type -> semantic_environment -> sem;
  187.                 sem -> ReportSemError(SemanticError::CIRCULAR_THIS_CALL,
  188.                                        constructor_block -> explicit_constructor_invocation_opt -> LeftToken(),
  189.                                        constructor_block -> explicit_constructor_invocation_opt -> RightToken(),
  190.                                        sem -> lex_stream -> Name(constructor_declarator -> identifier_token));
  191.             } while (called_constructor_declaration != constructor_declaration);
  192.         }
  193.     }
  194.  
  195.     return;
  196. }
  197.  
  198.  
  199. //
  200. // assert that the "index" of all types that should be checked is initially set to OMEGA
  201. //
  202. void TypeDependenceChecker::PartialOrder()
  203. {
  204.     for (FileSymbol *file_symbol = (FileSymbol *) file_set.FirstElement();
  205.                      file_symbol;
  206.                      file_symbol = (FileSymbol *) file_set.NextElement())
  207.     {
  208.         for (int j = 0; j < file_symbol -> types.Length(); j++)
  209.         {
  210.             TypeSymbol *type = file_symbol -> types[j];
  211.             if (type -> incremental_index == OMEGA)
  212.                 ProcessType(type);
  213.         }
  214.     }
  215.  
  216.     for (int k = 0; k < type_trash_bin.Length(); k++)
  217.     {
  218.         TypeSymbol *type = type_trash_bin[k];
  219.         if (type -> incremental_index == OMEGA)
  220.             ProcessType(type);
  221.     }
  222.  
  223.     return;
  224. }
  225.  
  226.  
  227. void TypeDependenceChecker::ProcessType(TypeSymbol *type)
  228. {
  229.     stack.Push(type);
  230.     int indx = stack.Size();
  231.     type -> incremental_index = indx;
  232.  
  233.     type -> dependents -> RemoveElement(type); // if dependents is reflexive make it non-reflexive - saves time !!!
  234.     type -> dependents_closure = new SymbolSet;
  235.     type -> dependents_cl